package algorithmExample.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: zhangrongqing
 * @Date: 2019/11/19 16:01
 */
//题目:https://leetcode-cn.com/problems/insert-interval/
public class InsertInterval {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0) {
            return new int[][]{newInterval};
        }
        List<int[]> listArray = new ArrayList<>();
        int curPos = 0;
        boolean flag = true;
        while (curPos < intervals.length) {
            if (intervals[curPos][1] >= newInterval[0] && flag) {
                int startVal = 0, endVal = 0;
                startVal = Math.min(newInterval[0], intervals[curPos][0]);
                while (curPos < intervals.length && newInterval[1] >= intervals[curPos][0]) {
                    endVal = Math.max(newInterval[1], intervals[curPos][1]);
                    curPos++;
                }
                listArray.add(new int[]{startVal, endVal});
                flag = false;
                continue;
            }
            listArray.add(intervals[curPos]);
            curPos++;
        }
        if (flag) {
            listArray.add(newInterval);
        }
        int[][] result = new int[listArray.size()][];
        for (int i = 0; i < listArray.size(); i++) {
            result[i] = listArray.get(i);
        }
        return result;
    }
}
